#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void SelectSort(int arr[], int size)
{
	if(NULL == arr || size < 1) {
		printf("Sort Error!\n");
		return;
	}

	int bound  = 0;
	int cur = 0;
	for(bound = 0; bound < size; ++bound) {
		for(cur = bound + 1; cur < size; ++cur) {
			if(arr[cur] < arr[bound]) {
				Swap(&arr[bound], &arr[cur]);
			}
		}
	}
}

void ArrPri(int arr[], int size)
{
	if(NULL == arr || size < 1) {
		printf("Printf Error!\n");
		return;
	}

	int i = 0;
	for(i = 0; i < size; ++i) {
		printf("%d  ", arr[i]);
	}
	printf("\n");
	return;
}

int* Intersection(int arr1[], int size_1, int arr2[], int size_2)
{
	if(size_1 < 1 || size_2 < 1 || NULL == arr1 || NULL == arr2) {
		printf("Error Input!\n");
		return NULL;
	}

	int index_1 = 0;
	int index_2 = 0;
	int result_index = 0;
	int resultSize = size_1 > size_2 ? size_2 : size_1;
	int sameNum = 0;

	int* resultArr = (int*)malloc(sizeof(int) * resultSize);
	if(NULL == resultArr) {
		printf("Malloc Failed!\n");
		return NULL;
	}

	SelectSort(arr1, size_1);
	ArrPri(arr1, size_1);
	SelectSort(arr2, size_2);
	ArrPri(arr2, size_2);

	while(index_1 < size_1 && index_2 < size_2) {
		if(arr1[index_1] < arr2[index_2]) {
			++index_1;
		}
		else if(arr1[index_1] > arr2[index_2]) {
			++index_2;
		}
		else {
			resultArr[result_index++] = arr1[index_1];
			++index_1;
			++index_2;
			++sameNum;
		}
	}
	ArrPri(resultArr, sameNum);
	return resultArr;
}

int main()
{
	int arr1[] = {9, 4, 2, 0, 8, 1, 6, 5, 3, 7};
	int arr2[] = {2, 9, 2, 5};
	int size_1 = sizeof(arr1)/sizeof(arr1[0]);
	int size_2 = sizeof(arr2)/sizeof(arr2[0]);

	// 求两个数组的交集，先排序，再遍历，这是暴力破解法，不适用于数据量很大的情况
	printf("交集 ： ")
	Intersection(arr1, size_1, arr2, size_2);

	return 0;
}
